import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;

public class PrimeNumbers {

	public static void main(String[] args) throws IOException {

		int number = Input.getInt("Enter the number ");
		System.out.println("Prime numbers up to " + number + ": ");
		System.out.print(getPrimesValues(number));
	}


	public static ArrayList<Integer> getPrimesValues(int maxLimit) {
		boolean[] keys = new boolean[maxLimit + 1];
		prepareSieve(keys);

		ArrayList<Integer> result = new ArrayList<>();
		for (int j = 0; j <= maxLimit; j++) {
			if (keys[j]) {
				result.add(j);
			}
		}
		return result;
	}

	public static void prepareSieve(boolean[] isPrime) {
		final int FIRST_PRIME = 2; // sieve for primes detection will start from
									// 2 - first prime number;
		Arrays.fill(isPrime, FIRST_PRIME, isPrime.length, true);
		isPrime[1] = false;

		for (int index = FIRST_PRIME; index * index < isPrime.length; index++) {
			if (isPrime[index]) {
				for (int step = index * index; step < isPrime.length; step += index) {
					isPrime[step] = false;
				}
			}
		}
	}

}
